1.Field
The present invention relates to a multi-tasking method of performing a plurality of tasks according to a priority of each of the plurality of tasks, and an embedded system therefor.
2.Description of the Related Art
Operating Systems (OSs) in embedded systems can be divided into Real Time OSs (RTOSs) and non-RTOSs. Representative RTOSs among commercialized OSs are VxWorks, pSOS, VRTX, QNX, Nucleus, MC/OSII, and OSE. These RTOSs commonly support preempted multi-tasking for stopping execution of a certain task and executing another task first.
In order for the RTOSs to support the preempted multi-tasking, each of the tasks must have a priority. Real-time in an RTOS means that an execution end time of a certain task must be in an expected schedule. In particular, when an execution end time of a specific task must be observed more severely than other tasks, the priority of the specific task is set higher compared to other tasks. For example, the shorter an execution period of a task is, the more severely an execution end time of the task must be observed. If priorities of tasks are inverted, execution end times of the tasks cannot be in an expected schedule, resulting in ruining the real-time characteristic in an RTOS.
FIG. 1 is a timing diagram to describe priority inversion in an RTOS.
Referring to FIG. 1, there exist three tasks, and durations in which each of the tasks is executed by occupying a Central Processing Unit (CPU) are marked. A first task having the lowest priority from among the three tasks preempts the CPU. The first task locks a mutex (Mutual Exclusion object) of a certain resource while occupying the CPU. In particular, portions in which the mutex is locked are marked darker from among the CPU occupation durations in FIG. 1. The mutex is an object to prevent a plurality of tasks from using a single resource at the same time. The fact that a task locks a mutex of a predetermined resource means that the task possesses the mutex of the predetermined resource, i.e., that only that task can use the predetermined resource. In addition, only that task can release the mutex lock of the predetermined resource.
Thereafter, a third task having a higher priority than that of the first task preempts the CPU. The third task attempts to lock the mutex of the resource while occupying the CPU. However, since the resource is mutex-locked by the first task, the third task cannot use the resource. As a result, the execution of the third task is blocked, and the execution of the first task resumes. Thereafter, a second task having a priority higher than that of the first task and lower than that of the third task preempts the CPU. The second task does not need the resource. Thus, the second task does not try the mutex lock of the resource and continuously occupies the CPU until the execution of the second task ends. As a result, an effect that the execution of the third task is delayed due to the execution of the second task having a lower priority than that of the third task, i.e., priority inversion, occurs.
In order to solve the priority inversion, various schemes have been suggested. Representative schemes are a Basic Priority Inversion (BPI) scheme and an Immediate Inheritance Protocol (IIP) scheme.
FIG. 2 is a flowchart of a multi-tasking method according to the BPI scheme in a conventional embedded system. In particular, the multi-tasking process illustrated in FIG. 2 is a mutex lock setting process from among an entire multi-tasking process.
Referring to FIG. 2, in operation 21, the embedded system searches for a task having the highest priority (hereinafter, “current task”) from among tasks that are ready to be executed.
The embedded system determines in operation 22 whether a mutex lock of a resource that is to be used by the current task found in operation 21 exists. If it is determined in operation 22 that the mutex lock does not exist, the process proceeds to operation 23, and if it is determined in operation 22 that the mutex lock exists, the process proceeds to operation 25.
The embedded system locks a mutex of the resource with respect to the current task in operation 23.
The embedded system executes the current task using the mutex locked resource in operation 24.
The embedded system compares a priority of the current task and a priority of a task which is using the resource in operation 25. If the priority of the current task is higher than the priority of the task possessing the mutex lock of the resource, the process proceeds to operation 26, otherwise the process proceeds to operation 28.
The embedded system increases the priority of the task possessing the mutex lock of the resource to the priority of the current task in operation 26.
The embedded system increases the priorities of tasks nested in the task possessing the mutex lock of the resource to the priority of the current task in operation 27.
The embedded system controls the current task to wait in operation 28 until the mutex lock of the resource does not exist, and the process proceeds to operation 22. Tasks nested in a task are tasks in a relationship that the latter task uses a result obtained by executing the former task. In particular, this priority increase scheme is called priority inheritance, which will now be described.
FIG. 3 is a diagram to describe the priority inheritance in BPI.
Referring to FIG. 3, a first task uses a resource corresponding to a second mutex, a second task outputs the resource corresponding to the second mutex and uses a resource corresponding to a fourth mutex, and a fourth task outputs the resource corresponding to the fourth mutex. In this case, if only the priority of the first task is increased to the priority of a current task, the execution of the first task is not blocked by a task having a lower priority than the priority of the current task, but the execution of the second task or the fourth task may be blocked by a task having lower priority than the priority of the current task. As a result, the resource corresponding to the second mutex, which is a result obtained by executing the second task, or the resource corresponding to the fourth mutex, which is a result obtained by executing the fourth task, is not output, and therefore, the first task may not use the resource corresponding to the second mutex.
Thus, an embedded system must increase the priorities of all tasks nested in a task possessing a mutex lock of a predetermined resource to the priority of a current task. However, this is a considerable overhead of embedded systems, and the real-time characteristic of embedded systems may be significantly ruined.
FIG. 4 is a flowchart of a multi-tasking method according to the IIP scheme in a conventional embedded system. In particular, the multi-tasking process illustrated in FIG. 4 is a mutex lock setting process from among an entire multi-tasking process.
Referring to FIG. 4, in operation 41, the embedded system searches for a task having the highest priority (hereinafter, “current task”) from among tasks that are ready to be executed.
The embedded system determines in operation 42 whether a mutex lock of a resource that is to be used by the current task found in operation 41 exists. If it is determined in operation 42 that the mutex lock does not exist, the process proceeds to operation 43, and if it is determined in operation 42 that the mutex lock exists, the process proceeds to operation 46.
The embedded system locks a mutex of the resource with respect to the current task in operation 43.
The embedded system increases the priority of the current task possessing the mutex lock to the highest priority of priorities of all tasks desiring to preempt a CPU in operation 44.
The embedded system executes the current task using the mutex-locked resource in operation 45.
The embedded system controls the current task to wait in operation 46 until the mutex lock of the resource does not exist, and the process proceeds to operation 42.
As described above, the IIP scheme may be very simple and effective. However, since the priority of a current task possessing a mutex lock is increased without any condition, if priority inversion does not occur, i.e., if the current task uses a different resource from that used by a task having a higher priority than that of the current task, the execution of the task having the higher priority than that of the current task may be delayed until the execution of the current task is completed. In particular, the IIP scheme may result in frequently blocking the execution of a task having a higher priority due to the execution of a task having a lower priority in a process in which a mutex lock duration frequently appears, significantly ruining the real-time characteristic of embedded systems.